package tree

import "math"

//给你一棵所有节点为非负值的二叉搜索树，请你计算树中任意两节点的差的绝对值的最小值。

//解决方案：中序遍历
//考虑对升序数组 aa 求任意两个元素之差的绝对值的最小值，答案一定为相邻两个元素之差的最小值.
//二叉搜索树有个性质为:二叉搜索树中序遍历得到的值序列是递增有序的，因此我们只要得到中序遍历后的值序列即能用上文提及的方法来解决。

//朴素的方法：经过一次中序遍历将值保存在一个数组中再进行遍历求解。
// 也可以在中序遍历的过程中用pre变量保存前驱节点的值，这样可以边遍历边更新答案，不再需要显式创建数组来保存。注意：pre的初始值需要设置成任意负数标记开头

//复杂度分析
//时间复杂度：O(n)，其中 nn 为二叉搜索树节点的个数。每个节点在中序遍历中都会被访问一次且只会被访问一次，因此总时间复杂度为 O(n)。
//空间复杂度：O(n),递归函数的空间复杂度取决于递归的栈深度，而栈深度在二叉搜索树为一条链的情况下会达到 O(n)级别。

func GetMinimumDifference(root *Node) int {
	ans, pre := math.MaxInt64, -1
	var dfs func(*Node)
	dfs = func(node *Node) {
		if node == nil {
			return
		}
		dfs(node.Left)
		if pre != -1 && int(math.Abs(float64(node.Val-pre))) < ans {
			ans = int(math.Abs(float64(node.Val - pre)))
		}
		pre = node.Val
		dfs(node.Right)
	}
	dfs(root)
	return ans
}
